const DoublyLinkedListNode = require('./DoublyLinkedListNode');

module.exports = class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  prepend(value) {
    // 生成一个next指向head的节点
    const node = new DoublyLinkedListNode(value, this.head);

    if (this.head) {
      // 原来的链表结构  A -> B -> null
      // 原来的链表结构  null <- A <- B
      // 插入节点后的链表结构 node -> A -> B -> null
      // 插入节点后的链表结构 null <- node <- A <- B
      // node.next = A
      // A.previous = node
      this.head.previous = node;
    }
    // 指针关系建立好之后，更新头部节点
    this.head = node;
    // 更新尾部节点
    if(!this.tail) {
      this.tail = node;
    }

    return this;
  }
  append(value) {
    const node = new DoublyLinkedListNode(value);

    // 1、尾部节点不存在
    if (!this.tail) {
      this.head = node;
      this.tail = node;
      return this;
    }
    // 2、尾部节点存在
    node.previous = this.tail;
    this.tail.next = node;

    // 3、更新尾部节点
    this.tail = node;

    return this;

  }
  delete(value) {
    // 删除节点，需要遍历整个节点

    // 如果链表是空的
    if(!this.head) {
      return null;
    }
    let deleteNode = null;
    let currentNode = this.head;

    while(currentNode) {
      if (currentNode.value === value) {
        deleteNode = currentNode;

        if (deleteNode === this.head) {
          // 要删除的节点是头部节点
          this.head = deleteNode.next;
          if (this.head) {
            // 更新头部节点的previous指针为null
            this.head.previous = null;
          }
          if (deleteNode === this.tail) {
            // 整个链表只有一个节点，head和tail都为null
            this.tail = null;
          }
        } else if (deleteNode === this.tail) {
          // 删除节点是尾部节点
          this.tail = deleteNode.previous;
          this.tail.next = null;
        } else {
          // 中间节点，分别记录节点的前后节点，更新对应的next和previous指针
          const prevNode = deleteNode.previous;
          const nextNode = deleteNode.next;

          prevNode.next = nextNode;
          nextNode.previous = prevNode;
        }
      }
      currentNode = currentNode.next;
    }
    return deleteNode;
  }
  find({value = undefined, callback = undefined}) {
    if (!this.head) {
      return null;
    }

    let currentNode = this.head;

    while(currentNode) {
      // 优先满足传入的回调函数
      if (callback && callback(currentNode.value)) {
        return currentNode;
      }
      if (value !== undefined && currentNode.value === value) {
        return currentNode;
      }

      currentNode = currentNode.next;
    }
    
    return null;
  }
  deleteTail() {
    if (!this.tail) {
      return null;
    }

    if (this.head === this.tail) {
      this.tail = null;
      this.head = null;
      return this.tail;
    }
    const deleteTail = this.tail;
    this.tail = deleteTail.previous;
    this.tail.next = null;
    return deleteTail;
  }
  deleteHead() {
    if (!this.head) {
      return null;
    }

    if (this.head === this.tail) {
      this.head = null;
      this.tail = null;
      return this.head;
    }

    const deleteHead = this.head;
    this.head = deleteHead.next;
    this.head.previous = null;
    return deleteHead;
  }
  // 节点转数组
  toArray() {
    const nodes = [];
    let currentNode = this.head;
    while(currentNode) {
      nodes.push(currentNode);
      currentNode = currentNode.next;
    }
    return nodes;
  }
  // 批量创建节点
  fromArray(values) {
    Array.isArray(values) && values.forEach(this.append);
    return this;
  }
  toString(callback) {
    return this.toArray().map(node => node.toString(callback)).toString();
  }
  // 反转链表
  reverse() {
    let currentNode = this.head;
    // 维护了两个同步指针，nextNode始终在prevNode的后面
    let nextNode = null;
    let prevNode = null;
    while(currentNode) {
      nextNode = currentNode.next;
      prevNode = currentNode.previous;

      currentNode.next = prevNode;
      currentNode.previous = nextNode;

      prevNode = currentNode;
      currentNode = nextNode;
    }

    this.head = prevNode;
    this.tail = this.head;

    return this;
  }
}